#pragma once
#include <cstdlib>
#include <cstring>

enum Direction {
    UP, DOWN, LEFT, RIGHT
};


union DirectionSet{
    struct {
        bool up: 1;
        bool down: 1;
        bool left: 1;
        bool right: 1;
    };
    struct {
        u_int8_t value:4;
        u_int8_t count:4;
    };
};

struct Cell {
    DirectionSet borders;
    bool visited:1;
};

struct WayPoint {
    int x;
    int y;
    WayPoint * prev;
    WayPoint(int x, int y, WayPoint * prev) {
        this->x = x;
        this->y = y;
        this->prev = prev;
    }
};

class Labirint;
class Filler;

class Cells {
private:
    Cell ** map;
    friend Labirint;
    friend Filler;
public:
    int sz_x;
    int sz_y;

    Cell * get(int x, int y) {
        return &map[x][y];
    }

    Cells(int sz_x, int sz_y) {
        this->sz_x = sz_x;
        this->sz_y = sz_y;
        map = (Cell **)malloc(sz_x * sizeof(Cell*));
        Cell fill_cell{};
        fill_cell.visited = false;
        fill_cell.borders.value = 0xF;
        for (int i=0;i<sz_x;i++) {
            map[i] = (Cell *)malloc(sz_y * sizeof(Cell));
            for (int j=0;j<sz_y;j++) {
                map[i][j] = fill_cell;
            }
        }
    }

    DirectionSet posible_expand(int x, int y) {
        DirectionSet ds = {0};
        if ((x>0) && (!map[x-1][y].visited)) {
            ds.left = true;
            ds.count++;
        }
        if ((x<sz_x-1) && (!map[x+1][y].visited)) {
            ds.right = true;
            ds.count++;
        }
        if ((y>0) && (!map[x][y-1].visited)) {
            ds.up = true;
            ds.count++;
        }
        if ((y<sz_y - 1) && (!map[x][y+1].visited)) {
            ds.down = true;
            ds.count++;
        }
        return  ds;
    }

    void step(Direction dir, int &x, int &y) {
        switch(dir) {
            case LEFT:
                map[x][y].borders.left = false;
                x--;
                map[x][y].borders.right = false;
                break;
            case RIGHT:
                map[x][y].borders.right = false;
                x++;
                map[x][y].borders.left = false;
                break;
            case UP:
                map[x][y].borders.up = false;
                y--;
                map[x][y].borders.down = false;
                break;
            case DOWN:
                map[x][y].borders.down = false;
                y++;
                map[x][y].borders.up = false;
                break;
        }
        map[x][y].visited = true;
    }

    ~Cells() {
        for (int i=0;i<sz_y;i++)
            free(map[i]);
        free(map);
    }
};


class Filler{
private:
    WayPoint * wp = nullptr;
    Cells * cells;
public:
    bool done = false;
    int x;
    int y;

    bool step() {
        if (done)
            return false;
        if (!wp) {
            this->wp = new WayPoint(x, y, nullptr);
            cells->map[this->x][this->y].visited = true;
        } else {
            DirectionSet pe = cells->posible_expand(this->x, this->y);
            if (!pe.value) {
                if (this->wp->prev == nullptr) {
                    this->done = true;
                    delete this->wp;
                    this->wp = nullptr;
                    return false;
                } else {
                    WayPoint * d = this->wp;
                    this->wp = wp->prev;
                    delete d;
                    this->x = wp->x;
                    this->y = wp->y;
                    return true;
                }
            } else {
                Direction dir;
                do {
                    dir = (Direction) (random() % 4);
                    if (pe.value & (1<<dir))
                        break;
                } while(true);
                cells->step(dir, x, y);
                wp = new WayPoint(x, y, wp);
                return true;
            }
        }
    }

    Filler(Cells * cells, int x, int y) {
        this->cells = cells;
        this->x = x;
        this->y = y;
    }
};


class Labirint {
private:
    static const int FILLERS_LIMIT = 1000;

    bool done = false;
    WayPoint * wp = nullptr;

    void add_filler(int x, int y) {
        if (fillers_count<FILLERS_LIMIT) {
            this->fillers[fillers_count] = new Filler(this->cells, x, y);
            fillers_count++;
        }
    }

public:
    Filler * fillers[FILLERS_LIMIT];
    int fillers_count = 0;
    Cells * cells;
    bool step() {
        bool res = false;
        for (int i=0;i<fillers_count;i++) {
            if (this->fillers[i])
                res|=this->fillers[i]->step();
            else
                break;
        }
        if (fillers_count<FILLERS_LIMIT) {
            int fc = fillers_count;
            for (int i = 0; i < fc; i++) {
                if ((random() % 1) == 0) {
                    DirectionSet ds = this->cells->posible_expand(fillers[i]->x, fillers[i]->y);
                    if (ds.count > 1)
                        add_filler(fillers[i]->x, fillers[i]->y);
                    if (ds.count > 2)
                        add_filler(fillers[i]->x, fillers[i]->y);
                }
                //cells->posible_expand()
            }
        }
        int fc = fillers_count;
        int idx = 0;
        for (int i=0;i<fc;i++) {
            if (fillers[i]->done) {
                delete fillers[i];
                fillers[i] = nullptr;
                fillers_count--;
            } else {
                fillers[idx] = fillers[i];
                if (idx!=i)
                    fillers[i] = nullptr;
                idx++;
            }
        }
        return res;
    }

    void generate() {
        while (this->step()) {
            //
        }
    };

    Labirint(int sz_x, int sz_y) {
        this->cells = new Cells(sz_x, sz_y);
        memset(this->fillers, 0, sizeof(this->fillers));
        add_filler(0, 0);
    }
    ~Labirint() {
        delete this->cells;
        for (int i=0;i<FILLERS_LIMIT;i++)
            delete this->fillers[i];
    }
};